from typing import *
from math import inf
from heapq import heappop, heappush


class Graph:

    def __init__(self, n: int, edges: List[List[int]]):
        g = [[] for _ in range(n)]
        for x, y, w in edges:
            g[x].append((y, w))
        self.g = g
        self.n = n

    def addEdge(self, e: List[int]) -> None:
        self.g[e[0]].append((e[1], e[2]))

    def shortestPath(self, s: int, e: int) -> int:
        dis = [inf] * self.n
        dis[s] = 0
        q = [(0, s)]
        while q:
            d, x = heappop(q)
            for y, w in self.g[x]:
                if d + w < dis[y]:
                    dis[y] = d + w
                    heappush(q, (dis[y], y))

        return -1 if dis[e] == inf else dis[e]


# Your Graph object will be instantiated and called as such:
# obj = Graph(n, edges)
# obj.addEdge(edge)
# param_2 = obj.shortestPath(node1,node2)
